package com.leetcode.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Dennis Li
 * @date 2020/7/21 22:23
 */
public class EraseOverlapIntervals_435 {

    public int eraseOverlapIntervals(int[][] intervals) {
        // 按照每个区间的终点来排序
        if (intervals.length == 0) return 0;
        // 按终点来进行排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
        // 记录剩余不需要移除的区间数目
        int res = 1;
        // 由于删除了区间，因此需要用end来记录上一个未被删除区间的结尾值
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                res++;
            }
        }
        // 记录的是重叠的个数，及不需要再移除的个数，因此最后要与总数做减法
        return intervals.length - res;
    }

}
